// #include <stdio.h>      // printf、sprintf 等
// #include <stdlib.h>     // malloc、calloc、free、qsort
// #include <string.h>     // strlen、strcpy、strcmp
// #include "uthash.h"     // 提供哈希表功能，如 HASH_FIND_STR、HASH_ADD_STR、HASH_ITER、HASH_DEL

// step 1# 定义常量
#define MAX_CNT 10000   // 每组最大字符串数量
#define MAX_LEN 101     // 每个字符串最大长度（含结束符）

// step 2# 定义字符串比较函数，用于 qsort 排序
int cmp (const void *a, const void *b) {
    char *aa = (char *)a;
    char *bb = (char *)b;
    return (*aa - *bb); // 按字符ASCII码升序排序
}

// step 3# 定义哈希表结构
struct HashMap {
    char *key;                              // 归类后排序字符串（哈希键）
    char array[MAX_CNT][MAX_LEN];           // 属于该组的原始字符串集合
    int num;                                // 当前组中字符串数量
    UT_hash_handle hh;                      // uthash 需要的句柄
};

struct HashMap *hashTable; // 全局哈希表
int g_groupSize;           // 分组数量

// step 4# 将字符串添加到对应的分组中
void AddGroup (char *key, char *member) {
    int len = strlen(member);
    struct HashMap *hashNode = NULL;

    HASH_FIND_STR(hashTable, key, hashNode); // 查找是否已有该分组

    if (hashNode == NULL) {
        // step 4.1# 若分组不存在，则新建分组
        hashNode = (struct HashMap *)calloc(1, sizeof(struct HashMap));
        hashNode->key = (char *)calloc((strlen(key) + 1), sizeof(char)); // 复制 key
        strcpy(hashNode->key, key);
        hashNode->num = 1;
        char *p = hashNode->array[0];
        strcpy(p, member); // 加入第一个成员
        HASH_ADD_STR(hashTable, key, hashNode); // 添加到哈希表中
        g_groupSize++; // 增加分组总数
    } else {
        // step 4.2# 分组存在，直接加入数组
        char *p = hashNode->array[hashNode->num];
        strcpy(p, member);
        hashNode->num += 1;
    }
    return;
}

// step 5# 释放哈希表内存
void FreeHashTable() {
    struct HashMap *hashNode, *tempNode;
    HASH_ITER(hh, hashTable, hashNode, tempNode) {
        free(hashNode->key);                // 释放 key 字符串内存
        HASH_DEL(hashTable, hashNode);     // 从哈希表中删除节点
        free(hashNode);                    // 释放节点本身
    }
    return;
}

// step 6# 主函数：分组异位词
char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) {
    // step 6.1# 初始化
    hashTable = NULL;
    g_groupSize = 0;

    // step 6.2# 遍历每个字符串，进行归类
    for (int i = 0; i < strsSize; i++) {
        struct HashMap *hashNode = NULL;
        char *curStr = strs[i];

        // 为排序副本分配内存（避免修改原字符串）
        char *sortStr = (char *)calloc((strlen(curStr) + 1), sizeof(char));
        strcpy(sortStr, curStr);

        qsort(sortStr, strlen(sortStr), sizeof(char), cmp); // 排序后作为 key

        AddGroup(sortStr, curStr); // 加入对应分组

        free(sortStr); // step 6.2.1# 释放排序副本内存
    }

    // step 6.3# 准备返回结果数组
    *returnSize = g_groupSize;
    *returnColumnSizes = (int *)calloc(g_groupSize, sizeof(int)); // 每组大小
    char ***ret = (char ***)calloc(g_groupSize, sizeof(char **)); // 返回的三维数组

    // step 6.4# 从哈希表中填充结果
    struct HashMap *cur, *temp;
    int index = 0;
    HASH_ITER(hh, hashTable, cur, temp) {
        (*returnColumnSizes)[index] = cur->num;
        int keyLen = strlen(cur->key);
        ret[index] = (char **)calloc(cur->num, sizeof(char *));
        for (int i = 0; i < cur->num; i++) {
            ret[index][i] = (char *)calloc((keyLen + 1), sizeof(char)); // 为每个字符串分配空间
            strcpy(ret[index][i], cur->array[i]);
        }
        index++;
    }

    // step 6.5# 清理哈希表
    FreeHashTable();
    hashTable = NULL;

    return ret;
}
